/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 找出字符串中第一个匹配项的下标
 */
#include "0.h"
// @lc code=start
class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> next(needle.length()+1,0);
        int prefix_len =0; 
        int i;
        for(i=1;i<needle.size();i++){
            if (needle[i]==needle[prefix_len]){
                prefix_len+=1;
                next[i]=prefix_len;
            }else{
                if(prefix_len==0){
                    next[i]=0;
                }else{
                    prefix_len=next[prefix_len-1];
                    i--;
                }
            }
        }

        i=0;
        int j=0;
        while(i<haystack.size()&&j<needle.size()){
            if(haystack[i]==needle[j]){
                i++;
                j++;
            }else if(j==0){
                i+=1;
            }else{
                j=next[j-1];
            }
        }

        return j==needle.size()?i-needle.size():-1;
    }
};
// @lc code=end

